package com.example.lcode.backtrack;

import java.util.Arrays;

/**
 * @version 1.0
 * @author: ChuJie_Lin
 * @since: 2021-12-13 12:13
 **/
public class Question698 {

    public boolean canPartitionKSubsets(int[] nums, int k) {
        int sum = Arrays.stream(nums).sum();
        if (sum % k != 0) {
            return false;
        }
        int avg = sum / k;
        int calc = 0;
        int count = 0;
        int beginIndex = nums.length - 1;
        Arrays.sort(nums);
        boolean[] sign = new boolean[nums.length];
        return canPartitionKSubsets(nums, k, calc, sign, avg, count, beginIndex);
    }

    private boolean canPartitionKSubsets(int[] nums, int k, int calc, boolean[] sign, int avg, int count,
                                         int beginIndex) {
        if (avg == calc) {
            count ++;
            calc = 0;
            beginIndex = nums.length - 1;
        } else if (calc > avg) {
            return false;
        }
        if (count == k) {
            return true;
        }
        boolean isTure = false;
        for (int i = beginIndex; i >= 0; i--) {
            if (!sign[i]) {
                sign[i] = true;
                isTure = canPartitionKSubsets(nums, k, calc + nums[i], sign, avg, count, i - 1);
                if (isTure) {
                    break;
                }
                sign[i] = false;
            }
        }
        return isTure;
    }


    public static void main(String[] args) {
        Question698 question698 = new Question698();
        int []arr = {4, 3, 2, 3, 5, 2, 1};
        int k = 4;
        boolean b = question698.canPartitionKSubsets(arr, k);
        System.out.println(b);
    }

}
